package com.kevin.Code.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname UniqueBinarySearchTreesii
 * @Description Leetcode 95. 不同的二叉搜索树 II 中等难度 思路不对 参考官方的题解
 * @Date 2021/12/31 19:18
 * @Version 1.0
 */
public class UniqueBinarySearchTreesii {


    /**
     * 思路对了一半 题意没有能够理解
     *
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1, n);
    }

    /**
     * 没理解题目的意思 思路是对的
     *
     * @param start
     * @param end
     * @return
     */
    public List<TreeNode> generateTrees(int start, int end) {

        List<TreeNode> curTrees = new LinkedList<>();

        if (start > end) {
            curTrees.add(null);
            return curTrees;
        }
        for (int i = start; i <= end; i++) {

            List<TreeNode> leftNodes = generateTrees(start, i - 1);
            List<TreeNode> rightNodes = generateTrees(i + 1, end);

            for (TreeNode leftNode : leftNodes) {
                for (TreeNode rightNode : rightNodes) {
                    TreeNode node = new TreeNode(i);
                    node.left = leftNode;
                    node.right = rightNode;
                    curTrees.add(node);
                }
            }
        }
        return curTrees;
    }


    public static void main(String[] args) {
        UniqueBinarySearchTreesii uniqueBinarySearchTreesii = new UniqueBinarySearchTreesii();
        List<TreeNode> list = uniqueBinarySearchTreesii.generateTrees(3);
    }

}
